The Web - PageRank.md (763B)
1 +++ 2 title = 'The Web - PageRank' 3 template = 'page-math.html' 4 +++ 5 # The Web - PageRank 6 uses hyperlinks to a page (indegrees) as criterion for importance of that page 7 8 $rank(p) = (\frac{1-d}{n}+d) \times \sum_{\overrightarrow{<q, p> \in E}} \frac{rank(q)}{\delta_{out}(q)}$ 9 10 d ∈ [0,1) is a constant damping factor, Google probably uses 0.85 11 12 $P[rank = k] \propto \frac{1}{k^{2.1}}$ 13 14 algorithm: 15 1. V = {v1, v2, …, vn}. t=0. d ≈ 0.85 16 2. PR(vi, t) = 1/n for all vi ∈ V 17 3. for all vi, calculate: 18 $PR(v_{i}, t+1) = \frac{1-d}{n} + d \times \sum_{\overrightarrow{<q, p> \in E}} \frac{PR(q, t)}{\delta_{out} (q)}$ 19 1. Increment t of one unit 20 2. Go to step 2 unless reached max number of iterations or 21 $\sum_{v \in V} PR(v, t) - PR(v, t-1)$ 22 is small enough